import { AVLTree } from './AVLTree'

class Node {
    constructor(key = null, value = null, next = null) {
        this.key = key
        this.value = value
        this.left = null
        this.right = null
        this.next = next
    }
}


export class LinkedListMap {
    constructor() {
        this.dummyHead = new Node()
        this.size = 0
    }

    getSize() {
        return this.size
    }

    isEmpty() {
        return this.size === 0
    }

    getNode(key) {
        let cur = this.dummyHead.next
        while (cur !== null) {
            if (cur.key == key) {
                return cur
            }

            cur = cur.next
        }
        return null
    }

    contains(key) {
        return this.getNode(key) != null
    }

    get(key) {
        const node = this.getNode(key)
        return node === null ? null : node.value
    }

    add(key, value) {
        const node = this.getNode(key)

        if (node === null) {
            this.dummyHead.next = new Node(key, value, this.dummyHead.next)
            this.size++

        } else {
            node.value = value

        }
    }

    set(key, value) {
        const node = this.getNode(key)
        if (node === null) {
            throw new Error(`${key} doesn't exist!`)
        }
        node.value = value
    }

    remove(key) {
        let prev = this.dummyHead
        while (prev.next !== null) {
            if (prev.next.key == key) {
                break
            }
            prev = prev.next
        }

        if (prev.next !== null) {
            const delNode = prev.next
            prev.next = delNode.next
            delNode.next = null
            this.size--
            return delNode.value
        }

        return null
    }

}


export class BSTMap {
    constructor() {
        this.root = null
        this.size = 0
    }

    getSize() {
        return this.size
    }

    isEmpty() {
        return this.size === 0
    }

    add(key, value) {
        this.root = this._add(this.root, key, value)
    }

    _add(node, key, value) {
        if (node === null) {
            this.size++
            return new Node(key, value)
        }

        if (node.key > key) {
            node.left = this._add(node.left, key, value)

        } else if (node.key < key) {
            node.right = this._add(node.right, key, value)

        } else {
            node.value = value

        }

        return node
    }

    getNode(node, key) {
        if (node === null) {
            return null
        }

        if (key === node.key) {
            return node

        } else if (key < node.key) {
            return this.getNode(node.left, key)

        } else {
            return this.getNode(node.right, key)

        }
    }

    contains(key) {
        return this.getNode(this.root, key) !== null
    }

    get(key) {
        const node = this.getNode(this.root, key)
        return node === null ? null : node.value
    }

    set(key, value) {
        const node = this.getNode(this.root, key)
        if (node === null) {
            throw new Error(`${key} doesn't exist!`)
        }
        node.value = value
    }

    remove(key) {
        const node = this.getNode(this.root, key)

        if (node !== null) {
            this.root = this._remove(this.root, key)
            return node.value
        }

        return null
    }

    _remove(node, key) {
        if (node === null) {
            return null
        }

        if (key < node.key) {
            node.left = this._remove(node.left, key)
            return node

        } else if (key > node.key) {
            node.right = this._remove(node.right, key)
            return node

        } else if (key === node.key) {

            if (node.left === null) {
                const rightNode = node.right
                node.right = null
                this.size--
                return rightNode
            }

            if (node.right === null) {
                const leftNode = node.left
                node.left = null
                this.size--
                return leftNode
            }

            // 待删除节点左右子树均不为空的情况
            // 找到比删除节点大的最小节点，即待删除节点右子树的最小节点
            // 用这个节点顶替待删除节点的位置
            const successor = this._minimum(node.right)
            successor.right = this._removeMin(node.right)
            successor.left = node.left

            node.left = node.right = null
            return successor
        }
    }

    minimum() {
        if (this.size === 0) {
            throw new Error('BST is empty.')
        }

        return this._minimum(this.root).val
    }

    _minimum(node) {
        if (node.left === null) {
            return node
        }

        return this._minimum(node.left)
    }

    maximum() {
        if (this.size === 0) {
            throw new Error('BST is empty.')
        }

        return this._maximum(this.root).val
    }

    _maximum(node) {
        if (node.right === null) {
            return node
        }

        return this._maximum(node.right)
    }

    removeMin() {
        const min = this.minimum()
        this.root = this._removeMin(this.root)
        return min
    }

    _removeMin(node) {
        if (node.left === null) {
            const rightNode = node.right
            node.right = null
            this.size--
            return rightNode
        }

        node.left = this._removeMin(node.left)
        return node
    }

    removeMax() {
        const max = this.maximum()
        this.root = this._removeMax(this.root)
        return max
    }

    _removeMax(node) {
        if (node.right === null) {
            const leftNode = node.left
            node.left = null
            this.size--
            return leftNode
        }

        node.right = this._removeMax(node.right)
        return node
    }
}


export class AVLMap {
    constructor() {
        this.avl = new AVLTree()
    }

    getSize() {
        return this.avl.getSize()
    }

    isEmpty() {
        return this.avl.isEmpty()
    }

    add(key, value) {
        this.avl.add(key, value)
    }

    contains(key) {
        return this.avl.contains(key)
    }

    get(key) {
        return this.avl.get(key)
    }

    set(key, value) {
        this.avl.set(key, value)
    }

    remove(key) {
        return this.avl.remove(key)
    }

}